package com.rem.se.my;

import java.util.Arrays;

/**
 * 插入排序
 * 稳定 o(n^2) 比冒泡交换次数少
 *
 * @author Rem
 * @date 2023-03-09
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] data = new int[]{4, 1, 7, 5, 6, 9, 2, 8, 3};

        for (int i = 1; i < data.length; i++) {
            //无序部分的第一位数字
            int t = data[i];
            //有序部分的最后一位下标
            int j = i - 1;
            while (j >= 0) {
                if (t < data[j]) {
                    data[j + 1] = data[j];
                    System.out.println("swap:" + Arrays.toString(data));
                } else {
                    break;
                }
                j--;
            }
            data[j + 1] = t;

            System.out.println("sort:" + Arrays.toString(data));
        }


    }
}
